package Tree;

public class _572_SubtreeofAnotherTree {
    //note:consider the situation that s's value>0
    public boolean isSubtree_1(TreeNode s, TreeNode t) {
        String ss = getVal(s);
        String ts = getVal(t);
        return ss.indexOf(ts) != -1;
    }

    public String getVal(TreeNode root) {
        if (root == null) {
            return "*";
        } else {
            String left = getVal(root.left);
            String right = getVal(root.right);
            return "-"+root.val+"-" + left + right;
        }
    }

    //reference solution:use recurtion
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s==null) return false;
        if (helper(s, t)) {
            return true;
        } else {
            return isSubtree(s.left, t) || isSubtree(s.right, t);
        }
    }
    public boolean helper(TreeNode s, TreeNode t) {
        if (s == null && t == null) {
            return true;
        }
        if (s == null || t == null) {
            return false;
        }
        if (s.val != t.val) {
            return false;
        }
        return helper(s.left, t.left) && helper(s.right, t.right);
    }
}
